To deal with the single-image scale-up problem, a super-resolution reconstruction algorithm based on dictionary learning and non-local similarity was proposed. The difference images between the high-resolution images and results of using iterative back-projection image reconstruction were obtained, and then the high and corresponding low dictionaries could be co-generated by training difference image patches and the corresponding low-resolution image patches via using K-Singular Value Decomposition (K-SVD) algorithm which was combined with the idea that the high and low dictionaries could be co-trained for super-resolution reconstruction. In addition, a non-local similarity regularization constraint was introduced in the new algorithm to further improve the quality of the reconstructed images. The experimental results show that the proposed algorithm achieves better results than learning-based algorithms in terms of both visual perception and objective evaluation.